import java.util.*;

/**
 * 面试题49：丑数
 */
public class Offer_49 {
    /**
     * 方法三：动态规划
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public int nthUglyNumber(int n) {
        // dp[i] 表示第 i 个丑数
        int[] dp = new int[n + 1];
        dp[1] = 1;
        // 下一个丑数是当前指针指向的丑数乘以对应的质因数
        int p2 = 1, p3 = 1, p5 = 1;

        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) {
                p2++;
            }
            if (dp[i] == num3) {
                p3++;
            }
            if (dp[i] == num5) {
                p5++;
            }
        }
        return dp[n];
    }

    /**
     * 方法二：最小堆
     * <p>
     * 时间复杂度：O(nlogn)。
     * n 次循环，每次从堆中取出一个元素，并最多加入 3 个元素，因此每次循环的复杂度为 O(logn)。
     * <p>
     * 空间复杂度：O(n)
     */
    public int nthUglyNumber2(int n) {
        int[] factors = { 2, 3, 5 };
        Set<Long> seen = new HashSet<>();
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        // HashSet 标记已访问的数字
        seen.add(1L);
        // 最小丑数 1 入堆
        heap.offer(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long cur = heap.poll();
            ugly = (int) cur;
            for (int factor : factors) {
                long next = cur * factor;
                // 如果该数字尚未被访问过，则入堆，并标记已访问
                if (seen.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return ugly;
    }

    /**
     * 方法一：暴力法（超时）
     * <p>
     * 计算出 int 范围中所有丑数
     */
    public int nthUglyNumber1(int n) {
        List<Integer> list = new ArrayList<>();
        for (long i = 1; i <= Integer.MAX_VALUE; i *= 2) {
            for (long j = i; j <= Integer.MAX_VALUE; j *= 3) {
                for (long k = j; k <= Integer.MAX_VALUE; k *= 5) {
                    list.add((int) k);
                }
            }
        }
        return list.get(n - 1);
    }
}
